
//? 堆排序的时间复杂度为O(n log n)，其中n是要排序的元素数量。
//? 堆排序的空间复杂度为O(1)，因为它是原地排序算法，不需要额外的空间。堆排序不是稳定的排序算法
function myHeapify(heap,i,len) {
    let max = i
    let left = 2 * i + 1
    let right = 2 * i + 2
    if (left < len && heap[left] < heap[max]) max = left
    if (right < len && heap[right] < heap[max]) max = right
    if (max !== i) {
        [heap[i], heap[max]] = [heap[max], heap[i]]
        myHeapify(heap,max,len)
    }
}
const nums = [5,13,24,35,22,79,86,75,64,53,29]
//? 第一步 建立最大堆（升序）从最后一个非叶子节点开始
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
    myHeapify(nums, i, nums.length)
}
//? 第二步 排序 一步步调整每个数
for (let i = nums.length - 1; i >= 0; i--) {
    //? 将尾叶子与根交换
    [nums[0], nums[i]] = [nums[i], nums[0]]
    //? 从头往下开始调整 这里i的变化就保证了不会去动已经处理过的位置了
    myHeapify(nums, 0, i)
}

